package com.zjj.algorithm.learning.atguigu.stack;

/**
 * 使用栈实现计算器功能
 *
 * 通过一个 index 值（索引），来遍历我们的表达式
 * 如果我们发现是一个数字, 就直接入数栈
 * 如果发现扫描到是一个符号, 就分如下情况
 *   1 如果发现当前的符号栈为 空，就直接入栈
 *   2 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符，
 *     就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，
 *     然后将当前的操作符入符号栈， 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
 * 当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
 * 最后在数栈只有一个数字，就是表达式的结果
 *
 * @author zjj_admin
 * @date 2022/11/9 13:59
 */
public class Calculator {

    public static void main(String[] args) {
        String expr = "70*1+2*6-4";
        //定义一个符号栈和数据栈
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);

        int index = 0;
        int num1;
        int num2;
        int oper;
        int res;
        //将每一次扫描到的字符保存到 ch 中
        char ch = ' ';
        String keepNum = "";
        while (true){
            //依次扫描表达式的每一个字符
            ch = expr.substring(index,index + 1).charAt(0);
            //判断 char 是什么，做相应的处理
            if (operStack.isOper(ch)) {
                //当如果是运算符的情况下
                //需要判断符号栈是否为空
                if ( !operStack.isEmpty()) {
                    //当符号栈不为null时，需要判断栈顶的符号和当前符号的优先级
                    //当当前的运算符优先级小于等于栈顶运算符的优先级，那么就需要从数栈中弹出两个数，和符号栈栈顶元素做运算，然后将新的运算符入栈
                    if(operStack.priority(ch) <= operStack.priority(operStack.peek())){
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1,num2,oper);
                        //将新的结果入栈
                        numStack.push(res);
                        //将新的操作符入栈
                        operStack.push(ch);

                    }else {
                        //当当前的运算符优先级小于符号栈顶运算符的优先级时，直接将运算符入栈
                        operStack.push(ch);
                    }

                }else {
                    //当符号栈为 null 时，直接入栈
                    operStack.push(ch);
                }
            }else {
                keepNum += ch;
                if(index >= expr.length() -1){
                    numStack.push(Integer.parseInt(keepNum));
                }else {
                    if(operStack.isOper(expr.substring(index+1,index+2).charAt(0))) {
                        // 如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
                        numStack.push(Integer.valueOf(keepNum));
                        // 清空（注意！！！）
                        keepNum = "";
                    }
                }
            }

            index ++;
            if(index >= expr.length()){
                break;
            }

        }


        while (true){
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1,num2,oper);
            //将新的结果入栈
            numStack.push(res);
        }
        int result = numStack.pop();
        System.out.printf("表达式 %s 的运算结果为：%d ",expr,result);


    }
}


/**
 * 基于数组，定义一个栈
 */
class ArrayStack2{
    private int maxSize;
    private  int[] stack;
    private int top = -1;

    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[this.maxSize];
    }

    public boolean isFull(){
        return this.top == this.maxSize -1;
    }

    public boolean isEmpty(){
        return top == -1;
    }

    /**
     * 入栈
     * @param value
     */
    public void push(int value){
        if (isFull()) {
            System.out.println("栈满，不能入栈");
            return;
        }
        top ++;
        stack[top] = value;
    }

    /**
     * 出栈
     * @return
     */
    public int pop(){
        if (isEmpty()) {
            throw new RuntimeException("栈已经空了");
        }
        int value = this.stack[top];
        top --;
        return value;
    }

    public void show(){
        if (isEmpty()) {
            System.out.println("栈中不存在数据");
            return;
        }
        for (int i = top ; i >= 0; i--){
            System.out.printf("stack[%d] = %d \n",i,stack[i]);
        }
    }

    /**
     * 查看栈顶的元素
     * @return
     */
    public int peek(){
        return this.stack[top];
    }

    /**
     * 返回运算符优先级，数字越大，优先级越高
     * @param oper
     * @return
     */
    public int priority(int oper) {
        if(oper == '*' || oper == '/') {
            return 2;
        }
        else if(oper == '+' || oper == '-') {
            return 1;
        }
        // 不满足的情况
        return -1;
    }


    public boolean isOper(char val){
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    /**
     * 计算方法
     * @param num1
     * @param num2
     * @param oper
     * @return
     */
    public int cal(int num1,int num2,int oper) {
        // res 用于存放计算的结果
        int res = 0;
        switch (oper) {
            case '+':
                res = num1+num2;
                break;
            case '-':
                res = num2-num1;
                break;
            case '*':
                res = num1*num2;
                break;
            case '/':
                res = num2/num1;
                break;
            default:
                break;
        }
        return res;
    }
}

